// https://leetcode.cn/problems/3sum/description/
package leet15sum3

import "sort"

// 思路一：
// 使用三重循环寻找符合相加之和为0的这个条件的这三个数。
// 为了保证不重复，做两个限制：
//    第一个限制是排序；第二个限制是每重循环提供的数字都要大于上一个数字。

func Sum3(nums []int) [][]int {
	// 定义一个二维切片，用于存储符合条件的三个数
	result := [][]int{}
	// 对数组进行排序
	sort.Ints(nums)
	// 遍历数组，寻找符合条件的三个数
	for i := 0; i < len(nums)-2; i++ {
		// 第一重循环就可以先决的过滤掉很多不符合条件的数字
		// 【过滤1】如果当前数字大于0，说明后面的数字都大于0，直接返回结果
		if nums[i] > 0 {
			break
		}
		// 【过滤2】如果当前数字和上一个数字相同，跳过
		if i > 0 && nums[i] == nums[i-1] {
			continue
		}
		// 第二重循环（先不使用左右指针，原始的循环）
		for j := i + 1; j < len(nums)-1; j++ {
			// 【过滤3】如果当前数字和上一个数字相同，跳过
			if j > i+1 && nums[j] == nums[j-1] {
				continue
			}
			// 第三重循环
			for k := j + 1; k < len(nums); k++ {
				// 【过滤4】如果当前数字和上一个数字相同，跳过
				if k > j+1 && nums[k] == nums[k-1] {
					continue
				}
				// 如果三个数相加为0，存入结果中
				if nums[i]+nums[j]+nums[k] == 0 {
					result = append(result, []int{nums[i], nums[j], nums[k]})
				}
			}
		}
	}
	return result
}

// 思路二：
// 使用双指针法，先对数组进行排序，然后使用两个指针分别指向数组的头和尾，
// 通过移动指针来寻找符合条件的三个数。
// 这种方法的时间复杂度为O(n^2)，空间复杂度为O(1)。
// 这种方法的时间复杂度比三重循环的方法要快很多，
// 但是空间复杂度还是O(n)，因为需要存储结果。
func Sum3_2(nums []int) [][]int {
	// 定义一个二维切片，用于存储符合条件的三个数
	result := [][]int{}
	// 对数组进行排序
	sort.Ints(nums)
	// 遍历数组，寻找符合条件的三个数
	for i := 0; i < len(nums)-2; i++ {
		// 第一重循环就可以先决的过滤掉很多不符合条件的数字
		// 【过滤1】如果当前数字大于0，说明后面的数字都大于0，直接返回结果
		if nums[i] > 0 {
			break
		}
		// 【过滤2】如果当前数字和上一个数字相同，跳过
		if i > 0 && nums[i] == nums[i-1] {
			continue
		}
		// 第二重循环（使用左右指针）
		left := i + 1
		right := len(nums) - 1
		for left < right {
			sum := nums[i] + nums[left] + nums[right]
			if sum == 0 {
				result = append(result, []int{nums[i], nums[left], nums[right]})
				left++
				right--
				// 【过滤3】如果当前数字和上一个数字相同，跳过
				for left < right && nums[left] == nums[left-1] {
					left++
				}
				for left < right && nums[right] == nums[right+1] {
					right--
				}
			} else if sum < 0 {
				// 因为我们是排好序的数组，此时我们想要寻找更大的数，所以让left指针向右移动
				left++
			} else {
				// 因为我们是排好序的数组，此时我们想要寻找更小的数，所以让right指针向左移动
				right--
			}
		}
	}
	return result
}
